package com.zhugang.week12;

/**
 * @program algorithms
 * @description: productExceptSelf
 * @author: chanzhugang
 * @create: 2022/09/08 14:03
 */
public class ProductExceptSelf {


    /**
     * 238 除自身外数组的乘积
     * 比较巧妙：前缀乘积、后缀乘积都用上
     *
     * @param nums
     * @return
     */
    public int[] productExceptSelf(int[] nums) {
        // 前缀、后缀乘积统计
        int n = nums.length;
        int[] leftProduct = new int[n];
        int[] rightProduct = new int[n];

        int product = 1;
        for (int i = 0; i < n; i++) {
            product *= nums[i];
            // 前缀统计乘积
            leftProduct[i] = product;
        }

        product = 1;

        for (int i = n - 1; i >= 0; i--) {
            product *= nums[i];
            // 后缀统计乘积
            rightProduct[i] = product;
        }

        int[] result = new int[n];
        for (int i = 0; i < n; i++) {
            result[i] = 1;
            // 除了它自身乘积 ： 前面的乘积 * 后面的乘积
            if (i - 1 >= 0) {
                result[i] *= leftProduct[i - 1];
            }
            if (i + 1 < n) {
                result[i] *= rightProduct[i + 1];
            }
        }
        return result;
    }
}